package com.hyb.algorithm.data.struct.dp;

/**
 * @author: ybhu
 * @create: 2021/09/20 22:42
 *
 * 650. 只有两个键的键盘
 * https://leetcode-cn.com/problems/2-keys-keyboard/
 *
 * https://www.bilibili.com/video/BV1Zq4y1N7JM
 */
public class KeysKeyboard {

    public int minSteps(int n) {

        int[] dp=new int[n+1];

        for(int i=2;i<=n;i++){
            dp[i]=i;
            for(int j=2;j*j<=i;j++){
                if(i%j==0){
                    dp[i]=dp[j]+dp[i/j];
                    break;
                }
            }
        }

        return dp[n];
    }
}
